package vernhe;

import java.util.Comparator;

public class RBTree<E> extends BBST<E> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    public RBTree() {
        this(null);
    }

    public RBTree(Comparator<E> comparator) {
        super(comparator);
    }

    private Node<E> red(Node<E> node) {
        return color(node,RED);
    }

    private Node<E> black(Node<E> node) {
        return color(node,BLACK);
    }

    private boolean colorOf(Node<E> node) {
        //空节点认为是BLACK
        return node == null ? BLACK : ((RBNode<E>)node).color;
    }

    private boolean isBlack(Node<E> node) {
        return colorOf(node) == BLACK;
    }

    private boolean isRed(Node<E> node) {
        return colorOf(node) == RED;
    }

    private Node<E> color(Node<E> node,boolean color) {
        if (node == null) {
            return null;
        }
        ((RBNode<E>)node).color = color;
        return node;
    }

    /**
     * 添加新节点后的处理
     *
     * @param node 新插入的节点
     */
    @Override
    protected void addAfter(Node<E> node) {
        Node<E> parent = node.parent;
        //是根节点
        if (parent == null) {
            System.out.println("根节点，只染黑");
            black(node);
            return;
        }
        //如果父节点是黑色，不做处理
        if (isBlack(parent)) {
            System.out.println("父节点是黑色的，不做处理");
            return;
        }
        //uncle节点是红色，进行丄溢，只进行染色即可
        Node<E> uncle = parent.sibling();
        //祖父节点
        Node<E> grand = red(parent.parent);
        if (isRed(uncle)) {
            System.out.println("叔父节点是红色的，染色，然后递归");
            black(parent);
            black(uncle);
            //把祖父节点当做是新添加的节点
            addAfter(grand);
        }else {
            //剩余的4种需要进行旋转的操作
            if (parent.isLeft()) {      //L
                if (node.isLeft()) {    //LL
                    System.out.println("LL");
                    black(parent);
                }else { //LR
                    System.out.println("LR");
                    black(node);
                    rotateLeft(parent);
                }
                rotateRight(grand);
            }else { //R
                if (node.isLeft()) {    //RL
                    System.out.println("RL");
                    black(node);
                    rotateRight(parent);
                }else { //RR
                    System.out.println("RR");
                    black(parent);
                }
                rotateLeft(grand);
            }
        }
    }


    /**
     * @param node 被删除节点或者用于取代被删除节点的节点
     */
    @Override
    protected void afterRemove(Node<E> node) {
        //如果node是red，染黑后返回，适用于传入node或者replacement
        //如果被替代节点是红色的，将其染成黑色，因为replacement会取代原来的node，而原来的node是黑色的
        if (isRed(node)) {
            black(node);
            return;
        }
        Node<E> parent = node.parent;
        //被删除的是根节点
        if (parent == null) {
            return;
        }

        //因为是叶子节点，在进入这个方法的时候,parent.left或者parent.right已经为null
        //加上node.isLeft()的原因是因为递归调用时传入的节点的parent的left或者right不为null
        boolean isLeft = parent.left == null || node.isLeft();
        // 判断被删除的节点是左边还是右边
        Node<E> sibling = isLeft ? parent.right : parent.left;

        if (isLeft) {
            //被删除节点是左边
            // 1.判断兄弟节点的颜色
            if (isRed(sibling)) {
                // 1.1转换成兄弟节点是黑色的情况
                black(sibling);
                red(parent);
                rotateRight(parent);
                // 1.2经过旋转，兄弟节点发生了变化
                sibling = parent.right;
            }

            // 2.兄弟节点是黑色的情况
            // 2.1判断是否可以借
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 2.1没有红色节点，借不了，产生下溢
                boolean parentIsBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentIsBlack) {
                    //如果说发生下溢的时候parent是黑色的，那么把它当作被删除的节点继续向上去操作
                    afterRemove(parent);
                }
            }else {
                // 2.2有红色节点，可以借
                // 2.2.1根据左边节点是否为红色来进行相应的旋转
                if (isBlack(sibling.right)) {
                    // 左边没有红色节点  LR  需要进行左旋转变成LL情况
                    rotateLeft(sibling);
                    //经过旋转后sibling发生变化
                    sibling = parent.right;
                }
                // 2.2.2左边是红色节点 LL 只进行右旋转即可，别忘了染色
                color(sibling,colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }
        }else {
            //被删除节点是右边的情况
            // 1.判断兄弟节点的颜色
            if (isRed(sibling)) {
                // 1.1转换成兄弟节点是黑色的情况
                black(sibling);
                red(parent);
                rotateLeft(parent);
                // 1.2经过旋转，兄弟节点发生了变化
                sibling = parent.left;
            }

            // 2.兄弟节点是黑色的情况
            // 2.1判断是否可以借
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 2.1没有红色节点，借不了，产生下溢
                boolean parentIsBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentIsBlack) {
                    //如果说发生下溢的时候parent是黑色的，那么把它当作被删除的节点继续向上去操作
                    afterRemove(parent);
                }
            }else {
                // 2.2有红色节点，可以借
                // 2.2.1根据左边节点是否为红色来进行相应的旋转
                if (isBlack(sibling.left)) {
                    // 左边没有红色节点  LR  需要进行左旋转变成LL情况
                    rotateLeft(sibling);
                    //经过旋转后sibling发生变化
                    sibling = parent.left;
                }
                // 2.2.2左边是红色节点 LL 只进行右旋转即可，别忘了染色
                color(sibling,colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }

    /**
     * 删除节点之后的操作
     *
     * @param node 新插入的节点
     * @param replacement 真正被删除的节点
     */
    /*
    @Override
    protected void afterRemove(Node<E> node,Node<E> replacement) {
        //如果node是red，不作任何处理
        if (isRed(node)) {
            return;
        }

        //下面的情况,node均为black
        //如果被替代节点是红色的，将其染成黑色，因为replacement会取代原来的node，而原来的node是黑色的
        if (isRed(replacement)) {
            black(replacement);
            return;
        }
        Node<E> parent = node.parent;
        //被删除的是根节点
        if (parent == null) {
            return;
        }

        //因为是叶子节点，在进入这个方法的时候,parent.left或者parent.right已经为null
        //加上node.isLeft()的原因是因为递归调用时传入的节点的parent的left或者right不为null
        boolean isLeft = parent.left == null || node.isLeft();
        // 判断被删除的节点是左边还是右边
        Node<E> sibling = isLeft ? parent.right : parent.left;

        if (isLeft) {
            //被删除节点是左边
            // 1.判断兄弟节点的颜色
            if (isRed(sibling)) {
                // 1.1转换成兄弟节点是黑色的情况
                black(sibling);
                red(parent);
                rotateRight(parent);
                // 1.2经过旋转，兄弟节点发生了变化
                sibling = parent.right;
            }

            // 2.兄弟节点是黑色的情况
            // 2.1判断是否可以借
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 2.1没有红色节点，借不了，产生下溢
                boolean parentIsBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentIsBlack) {
                    //如果说发生下溢的时候parent是黑色的，那么把它当作被删除的节点继续向上去操作
                    afterRemove(parent,null);
                }
            }else {
                // 2.2有红色节点，可以借
                // 2.2.1根据左边节点是否为红色来进行相应的旋转
                if (isBlack(sibling.right)) {
                    // 左边没有红色节点  LR  需要进行左旋转变成LL情况
                    rotateLeft(sibling);
                    //经过旋转后sibling发生变化
                    sibling = parent.right;
                }
                // 2.2.2左边是红色节点 LL 只进行右旋转即可，别忘了染色
                color(sibling,colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }
        }else {
            //被删除节点是右边的情况
            // 1.判断兄弟节点的颜色
            if (isRed(sibling)) {
                // 1.1转换成兄弟节点是黑色的情况
                black(sibling);
                red(parent);
                rotateLeft(parent);
                // 1.2经过旋转，兄弟节点发生了变化
                sibling = parent.left;
            }

            // 2.兄弟节点是黑色的情况
            // 2.1判断是否可以借
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 2.1没有红色节点，借不了，产生下溢
                boolean parentIsBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentIsBlack) {
                    //如果说发生下溢的时候parent是黑色的，那么把它当作被删除的节点继续向上去操作
                    afterRemove(parent,null);
                }
            }else {
                // 2.2有红色节点，可以借
                // 2.2.1根据左边节点是否为红色来进行相应的旋转
                if (isBlack(sibling.left)) {
                    // 左边没有红色节点  LR  需要进行左旋转变成LL情况
                    rotateLeft(sibling);
                    //经过旋转后sibling发生变化
                    sibling = parent.left;
                }
                // 2.2.2左边是红色节点 LL 只进行右旋转即可，别忘了染色
                color(sibling,colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }
    */

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RBNode(element, parent);
    }

    private static class RBNode<E> extends Node<E> {
        boolean color = RED;
        public RBNode(E element, Node<E> parent) {
            super(element, parent);
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (root == null) return "";
        return toString(root,sb,"");
    }

    @Override
    protected String toString(Node<E> node, StringBuilder sb, String perfix) {
        if (node.left != null) toString(node.left,sb,perfix + "[L]");
        if (isRed(node)) sb.append(perfix).append("【Red-").append(node.element).append("】").append("\n");
        else sb.append(perfix).append("【").append(node.element).append("】").append("\n");
        if (node.right != null) toString(node.right,sb,perfix + "[R]");
        return sb.toString();
    }
}
